package Back;

/**
 * @author zhang kun
 * @Classname HeapSort
 * @Description TODO
 * @Date 2021/8/21 17:18
 */
import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/17.
 * 堆排序demo
 */
public class HeapSort {
    public static void main(String []args){

        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr){
        for(int i = arr.length/2 -1;i>=0;i--){
            adjust(arr,i,arr.length);
        }
        for(int i = arr.length -1;i>=1;i--){
            swap(arr,0,i);
            adjust(arr,0,i);
        }
    }

    private static void swap(int[] arr, int i, int i1) {
        int temp = arr[i];
        arr[i] = arr[i1];
        arr[i1] = temp;
    }

    private static void adjust(int[] arr, int begin, int end) {
        int temp = arr[begin];
        for(int i = begin*2+1;i<end;i=2*i+1){
            if(i+1<end && arr[i] < arr[i+1]){
                i++;
            }
            if(arr[i] > temp){
                arr[begin] = arr[i];
                begin = i;
            }
        }
        arr[begin] = temp;
    }
}
